package mo.tags.backtrack;

import java.util.*;

public class L17 {

    private static Map<Character, List<Character>> digit2alp = new HashMap<>();

    static {
        digit2alp.put('2', Arrays.asList('a', 'b', 'c'));
        digit2alp.put('3', Arrays.asList('d', 'e', 'f'));
        digit2alp.put('4', Arrays.asList('g', 'h', 'i'));
        digit2alp.put('5', Arrays.asList('j', 'k', 'l'));
        digit2alp.put('6', Arrays.asList('m', 'n', 'o'));
        digit2alp.put('7', Arrays.asList('p', 'q', 'r', 's'));
        digit2alp.put('8', Arrays.asList('t', 'u', 'v'));
        digit2alp.put('9', Arrays.asList('w', 'x', 'y', 'z'));
    }

    public List<String> letterCombinations(String digits) {
        if (digits.length() <= 0) {
            return Collections.emptyList();
        }
        LinkedList<StringBuilder> res = new LinkedList<>();
        for (int i = 0; i < digits.length(); i++) {
            List<Character> tmp = digit2alp.get(digits.charAt(i));
            if (res.isEmpty()) {
                for (char c : tmp) {
                    res.add(new StringBuilder().append(c));
                }
            } else {
                int size = res.size();
                while (size > 0) {
                    StringBuilder pop = res.removeFirst();
                    for (char c : tmp) {
                        StringBuilder copy = new StringBuilder(pop);
                        copy.append(c);
                        res.add(copy);
                    }
                    size--;
                }
            }
        }
        List<String> ans = new ArrayList<>();
        while (!res.isEmpty()) {
            ans.add(res.pop().toString());
        }
        return ans;
    }

}
